package com.yun.datastructure.linear.list.linkedlist.leetcode;

import com.yun.datastructure.linear.list.linkedlist.ListNode;

public class Leetcode234 {

    public boolean isPalindrome(ListNode head) {
        ListNode p1 = head;//慢
        ListNode p2 = head;//快
        ListNode n1 = null;
        ListNode o1 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
            p2 = p2.next;

            //反转链表
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }

        if(p2!=null){//奇数节点
            p1=p1.next;
        }

        while (n1 != null) {
            if (p1.val != n1.val) {
                return false;
            } else {
                p1 = p1.next;
                n1 = n1.next;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 4, 3, 2, 1);
        boolean n1 = new Leetcode234().isPalindrome(head);
        System.out.println(n1);
    }
}
